from typing import List
import collections

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        map = dict()
        m = len(preorder)
        n = len(inorder)
        for i in range(n):
            map[inorder[i]] = i

        def dfs(p_start, p_end, i_start, i_end):
            if p_start>p_end or i_start >i_end:
                return None

            i_postion = map[preorder[p_start]]
            head = TreeNode(preorder[p_start])

            head.left = dfs(p_start+1, p_start+(i_postion-i_start), i_start, i_postion-1);
            head.right = dfs(p_start+(i_postion-i_start)+1, p_end, i_postion+1, i_end)

            return head
        
        return dfs(0, m-1, 0, n-1)

